package mergeKLists;

import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class Solution {
      public class ListNode {
          int val;
          ListNode next;
          ListNode() {}
          ListNode(int val) { this.val = val; }
          ListNode(int val, ListNode next) { this.val = val; this.next = next; }
      }

    public ListNode mergeKLists(ListNode[] lists) {
          // 思路一 小顶堆 优先级队列
//        PriorityQueue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
//            @Override
//            public int compare(ListNode o1, ListNode o2) {
//                return o1.val - o2.val;
//            }
//        });
//        for (int i = 0; i < lists.length; i++) {
//            if(lists[i]!=null){
//                queue.offer(lists[i]);
//            }
//        }
//        for (ListNode n: queue) {
//            System.out.println(n.val);
//        }
//        ListNode ans = new ListNode();
//        ListNode p = ans;
//        while(queue.size()>1){
//            ListNode node = queue.poll();
//            if(node.next!=null){
//                queue.offer(node.next);
//            }
//            p.next = node;
//            p = p.next;
//        }
//        return ans.next;

        // 思路二 两个两个合并
        ListNode ans = lists[0];
        for (int i = 1; i < lists.length; i++) {
            ans = mergeTwoLists(ans,lists[i]);
        }
        return ans;
    }
    // 合并两个链表
    private ListNode mergeTwoLists(ListNode a,ListNode b) {
        if (a == null || b == null) {
            return a != null ? a : b;
        }
        ListNode head = new ListNode(0);
        ListNode p = head;
        ListNode p1 = a;
        ListNode p2 = b;
        while(p1!=null&&p2!=null){
            if(p1.val<p2.val){
                p.next = p1;
                p1 = p1.next;
            }else {
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }
        p.next = p1!=null?p1:p2;
        return head.next;
    }
}
